import java.util.*;
/**
 * 
 * 设计LRU缓存结构
 * 
 * 描述

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:
1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

提示:
1.某个key的set或get操作一旦发生，则认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过capacity时，移除最不经常使用的记录。
3.返回的value都以字符串形式表达，如果是set，则会输出"null"来表示(不需要用户返回，系统会自动输出)，方便观察
4.函数set和get必须以O(1)的方式运行
5.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹
数据范围:
1
≤
c
a
p
a
c
i
t
y
<
=
1
0
5
1≤capacity<=10 
5
 
0
≤
k
e
y
,
v
a
l
≤
2
×
1
0
9
 
0≤key,val≤2×10 
9
  
1
≤
n
≤
1
0
5
1≤n≤10 
5
 

 */
public class 设计LRU缓存结构 {
    
    public static void main(String[] args) {
        
        
    }

    Map<Integer, Integer> map;
    int capacity;
    public 设计LRU缓存结构(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>(capacity);
    }

    public int get(int key) {
        Integer value = map.get(key);
        if (value != null) { // 如果已经有此key
            if (map.size() > 1) {
                map.remove(key); // 删除原先的key
                map.put(key, value); // 添加key到最后
            }
        } else {
            return -1;
        }
        return value;
    }

    public void set(int key, int value) {
        if (map.containsKey(key)) { // 已经有此key
            map.remove(key); // 删除原先的key
        } else if (map.size() >= capacity) { // 容量达到了最大
            Integer firstKey = map.keySet().iterator().next();
            map.remove(firstKey); // 删除第一个key
        }
        map.put(key, value); // 添加key到最后
    }
}
